package 周赛._278;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/all-divisions-with-the-highest-score-of-a-binary-array/
 */
public class _5981_分组得分最高的所有下标 {
    /**
     * 双指针
     * 因为是二进制数组  因此 只有 0 或 1
     * left 记录 0 的数量  right 记录 1 的数量
     * @param nums 目标传入的数组
     * @return List<Integer>
     */
    public List<Integer> maxScoreIndices(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int left = 0, right = 0;
        int n = nums.length;
        // 计算 1 的数量
        for (int num : nums) {
            right += num;
        }
        int[] ret = new int[n + 1];
        // 记录为 1 的数量
        ret[0] = right;
        // 记录为 0 的数量
        ret[n] = n - right;
        // 取最大值 即 1 的数量或 0 的数量
        int max = Math.max(ret[0], ret[n]);
        for (int i = 1; i < n; i++) {
            // 遍历移动
            if (nums[i - 1] == 0) {
                left++;
            } else {
                right--;
            }
            ret[i] = left + right;
            max = Math.max(ret[i], max);
        }
        // 遍历查找与最大值相同的次序
        for (int i = 0; i < n + 1; i++) {
            if (ret[i] == max) {
                ans.add(i);
            }
        }
        return ans;
    }
}
